package com.xie.leetcode.array;

//915. 分割数组
//        给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
//
//        left 中的每个元素都小于或等于 right 中的每个元素。
//        left 和 right 都是非空的。
//        left 的长度要尽可能小。
//        在完成这样的分组后返回 left 的 长度 。
//
//        用例可以保证存在这样的划分方法。
//
//        示例 1：
//
//        输入：nums = [5,0,3,8,6]
//        输出：3
//        解释：left = [5,0,3]，right = [8,6]
//        示例 2：
//
//        输入：nums = [1,1,1,0,6,12]
//        输出：4
//        解释：left = [1,1,1,0]，right = [6,12]
//
//        提示：
//
//        2 <= nums.length <= 105
//        0 <= nums[i] <= 106
//        可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

/**
 * @author xiezhendong
 * @date 2022/10/24
 */
public class PartitionDisjoint {

    public static void main(String[] args) {
        PartitionDisjoint partitionDisjoint = new PartitionDisjoint();
        int[] nums = new int[]{5, 0, 3, 8, 6};
        System.out.println(partitionDisjoint.partitionDisjoint(nums));
        nums = new int[]{1, 1, 1, 0, 6, 12};
        System.out.println(partitionDisjoint.partitionDisjoint(nums));
    }

    public int partitionDisjoint(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] minRight = new int[n];
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.min(nums[i], minRight[i + 1]);
        }

        int length = 0;
        int numMaxValue = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int numValue = nums[i];
            numMaxValue = Math.max(numMaxValue, numValue);
            boolean isReturn = false;

            if (i == nums.length - 1) {
                isReturn = true;
            } else {
                int min = minRight[i + 1];
                if (numMaxValue <= min) {
                    isReturn = true;
                }
            }

            if (Boolean.TRUE.equals(isReturn)) {
                length = i + 1;
                break;
            }
        }
        return length;
    }
}
